import time


class Solution:
    def coinChange(self, coins: list, amount: int) -> int:
        """没明白为啥会超时"""
        dp = [0]
        length, money = len(coins), 0
        coin_list = [0] * length
        money_list = [0]
        while money < amount:
            money = min(money_list[coin_list[i]] + coins[i] for i in range(length))
            for i in range(length):
                if money_list[coin_list[i]] + coins[i] == money:
                    try:
                        count = min(dp[coin_list[i]], count)
                    except:
                        count = dp[coin_list[i]]
                    coin_list[i] += 1
            money_list.append(money)
            dp.append(count + 1)
            count = None
        if money == amount:
            return dp[-1]
        else:
            return -1


class Solution2:
    def coinChange(self, coins: list, amount: int) -> int:
        dp = [[0, 0]]
        length = len(coins)
        coin_list = [0] * length
        while dp[-1][0] < amount:
            money = min(dp[coin_list[i]][0] + coins[i] for i in range(length))
            for i in range(length):
                if dp[coin_list[i]][0] + coins[i] == money:
                    try:
                        count = min(dp[coin_list[i]][1], count)
                    except:
                        count = dp[coin_list[i]][1]
                    coin_list[i] += 1
            dp.append([money, count + 1])
            count = None
        if dp[-1][0] == amount:
            return dp[-1][1]
        else:
            return -1


class Solution:
    def coinChange(self, coins: list, amount: int) -> int:
        dp = [-1] * (amount + 1)
        dp[0] = 0
        for i in range(1, amount + 1):
            for coin in coins:
                if i - coin >= 0 and dp[i - coin] >= 0:
                    dp[i] = min(dp[i - coin] + 1, dp[i]) if dp[i] != -1 else dp[i - coin] + 1
        return dp[-1]


class Solution:
    """这个最后最快"""
    def coinChange(self, coins: list, amount: int) -> int:
        dp = [-1] * (amount + 1)
        dp[0] = 0
        for i in range(1, amount + 1):
            mid_list = [dp[i - coin] for coin in coins if i - coin >= 0 and dp[i - coin] != -1]
            dp[i] = min(mid_list) + 1 if mid_list else -1
        return dp[-1]


a = Solution()
now = time.time()
print(a.coinChange(coins=[1, 2, 5], amount=11))  # 3
print(a.coinChange(coins=[2], amount=3))  # -1
print(a.coinChange(coins=[1], amount=0))  # 0
print(a.coinChange([461, 307, 4, 97, 352, 446, 479, 243], 7265))  # 16
print(a.coinChange([463, 351, 30, 129, 434, 91, 120, 205, 205], 4863))  # 13
print(time.time() - now)
